1. Field of the Invention
The present invention relates to digital image processing and more particularly to systems and methods for encoding and decoding electronic image data.
2. Description of the Prior Art
The following references disclose systems representative of the prior art in the field of electronic image processing.
R. Hunter and A. H. Robinson, "International digital facsimile coding standards", Proceedings of the IEEE, Vol 68, No 7, pp. 854-867, (Jul. 1980).
D. A. Huffman, "A method for the construction of minimum redundancy codes", Proc. IRE, vol. 40, pp. 1097-1101, (Sept. 1952).
A. J. Frank, "Uniform decoding of minimum-redundancy codes", U.S. Pat. No. 3,883,847, May 13, 1975.
H. Meyr, H. G. Rosdolsky, and T. S. Huang, "Optimum Run Length Codes", IEEE Trans. Comm. Vol COM-22, No 6, pp. 826-835 (Jun. 1974).
G. Goertzel and J. L. Mitchell, "Two-Dimensional Image Data Compression and Decompression System", U.S. Defensive Publication #T985,005, Aug. 7, 1979.
D. C. Van Voorhis, "Variable-length to fixed-length conversion of minimum-redundancy codes", U.S. Pat. No. 4,044,347, Aug. 23, 1977.
W. S. Michel, W. O. Fleckenstein and E. R. Kretzmer, "A Coded Facsimile System", IRE Wescon Conv. Rec. pp. 84-93 (1957).
Bahl, L. R., D. I. Barnea, and H. Kobayashi, "Image Compaction System", U.S. Pat. No. 3,833,900 (1974).
DELTA INFORMATION SYSTEMS, Inc., "Group 3 Facisimile Apparatus for Document Transmission", Appendix B, Final Report to National Communications System, Aug. 16, 1982.
With particular regard to the patented art:
U.S. Pat. No. 3,927,251 to White et al shows an apparatus and method for detection and control of errors in two dimensionally compressed image data;
U.S. Pat. Nos. 4,040,093 and 4,121,258 to Nakagome et al show methods for coding a facsimile signal employing two dimensional coding;
U.S. Pat. No. 4,103,287 to Frank shows a method for encoding an image signal employing image partitioning;
U.S. Pat. No. 3,927,251 shows a method for coding a facsimile signal employing detection and control of errors;
U.S. Pat. No. 3,830,965 to Beaudette shows a method for coding a facsimile signal employing one of two preselected encoding modes;
U.S. Pat. No. 4,028,731 to Arps et al shows a method for encoding an image signal employing cross array correlation; and
U.S. Pat. No. 3,675,211 to Raviv shows a method for data compaction employing a three state associative memory.
It will be seen that Huffman describes in the Proc. IRE, Sept. 1952, article, a simple way to construct a minimum redundancy variable length code. The code word lengths are related to the frequencies of the source messages, the more frequent messages being assigned shorter code words. Such Huffman codes have been shown to be the optimum coding for an ensemble of messages. However, they have one major disadvantage over other (suboptimum) techniques for variable-length codes in that they are random patterns. This complicates the decoding process.
There is usually a tradeoff between speed of decoding and the size of the decode tables. Frank in U.S. Pat. No. 3,883,847 describes a table lookup for parallel decoding which is a compromise between speed and table storage. Meyr et al in IEEE Trans. Comm. Jun. 1974 looked for special classes which could be easily implemented by having the code words be multiples of fixed length blocks.
The CCITT one-dimensional (described in Hunter et al in Jul. 1980) run length standard uses a Modified Huffman code. The runs from 0-63 are individually coded while longer runs are constructed from codes for the multiples of 64 followed by a code for the remaining length of 0-63. Separate tables are used for the white and black runs since they have rather different distributions.
One way to implement a serial decode of the CCITT run lengths is by table lookup a bit at a time.
In Goertzel et al (T985,005) the least significant bit of the address into the ROM table is the next code bit. One of the output bits flags whether to continue decoding using the remaining output bits as the next table address or to stop because a complete code has been encountered. Then the output gives the run length size. The table could just as easily have the next code bit as the most significant bit. That case is equivalent to separate tables according to whether the next bit was a `0` or `1`.